home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 118_01 / symtab.bds < prev    next >
Encoding:
Text File  |  1980-07-08  |  9.0 KB  |  445 lines
  1. /* Symbol table routines for Software Tools
  2.  * source:  symtab.bds
  3.  * version: November 27, 1981
  4.  */
  5.  
  6. #include tools.h
  7.  
  8. /* These routines assume that the data field in each node
  9.  * has the following format:
  10.  *
  11.  *    name field:   string, ends with EOS.
  12.  *    value field:  string, ends with EOS.
  13.  *
  14.  * The length of these fields is arbritrary;
  15.  * that is why they are not made part of struct node.
  16.  * The table lookup routines examine only the name field.
  17.  * This format works well for macros, but may not be so
  18.  * good for numeric fields which may contain embedded EOS
  19.  * characters.
  20.  */
  21.  
  22. /* format of each symbol table */
  23.  
  24. struct symtab {
  25.     char stchk;        /* check byte */
  26.     int  htsize;        /* size of hash table */
  27.     struct node *hashtab [1]; /* start of hash table */
  28. };
  29.  
  30. #define TABCHK "T"    /* only legal value for stchk */
  31. #define STHEAD 3    /* size of fixed part of symtab */
  32.  
  33. /* format of each node */
  34.  
  35. struct node {
  36.     char nchk;        /* check byte */
  37.     struct node *next;    /* pointer to next node */
  38.     char data [1];        /* first byte of data field */
  39. };
  40.  
  41. #define NODE  "N"    /* only legal value for nchk  */
  42. #define NHEAD 3        /* size of fixed part of node */
  43.  
  44. /* These routines have different calling sequences from
  45.  * the RATFOR routines from the Software Tools Users Group:
  46.  *
  47.  *
  48.  *  RATFOR:  delete (symbol, table)
  49.  *           char *symbol, *table;
  50.  *
  51.  *  C:       delete (symbol, table)
  52.  *           char *symbol;
  53.  *           struct symtab *table;
  54.  *           
  55.  *
  56.  *  RATFOR:  enter (symbol, info, table)
  57.  *           char *symbol;
  58.  *           int info;
  59.  *           char *table;
  60.  *
  61.  *  C:       enter (symbol, info, table)
  62.  *           char *symbol, *info;
  63.  *           struct symtab *table;
  64.  *
  65.  *
  66.  *  RATFOR:  lookup (symbol, info, table)
  67.  *           char *symbol, *info, *table;
  68.  *           (copy information to info []);
  69.  *
  70.  *  C:       lookup (symbol, table)
  71.  *           char *symbol;
  72.  *           struct symtab *table;
  73.  *           (return pointer to info field)
  74.  *           
  75.  *
  76.  *  RATFOR:  mktabl (nodesize)
  77.  *           int nodesize;
  78.  *
  79.  *  C:       mktable (htsize)
  80.  *           int htsize;
  81.  *
  82.  *
  83.  *  RATFOR:  rmtabl (table)
  84.  *           char *table;
  85.  *
  86.  *  C:       rmtabl (table)
  87.  *           struct symtab *table;
  88.  *
  89.  *
  90.  *  RATFOR:  sctabl (table, sym, info, posn)
  91.  *           char *table, *sym, *info;
  92.  *           int *posn;
  93.  *           (copy fields to sym [] and info [])
  94.  *
  95.  *  C:       sctabl (table, posn)
  96.  *           struct symtab *table;
  97.  *           int *posn;
  98.  *           (return pointer to data field of node)
  99.  *
  100.  */
  101.  
  102. #define NTABS 10        /* number of symbol tables */
  103.  
  104. main(argc, argv)
  105. int argc;
  106. char **argv;
  107. {
  108.     initst(argc, argv);
  109.     main1();
  110.     endst();
  111. }
  112.  
  113. main1()
  114. {
  115.     char inbuf[100];    /* input buffer */
  116.     int  i, number;
  117.  
  118.     char *tables [NTABS];    /* pointer to symbol tables */
  119.     char symbol [100];    /* symbol name */
  120.     char info [100];    /* info field of symbol */
  121.  
  122.     /* init available memory */
  123.     dsinit();
  124.     printf("\nTest of symtab.bds:  August 27, 1981\n");
  125.     for (i = 0; i < NTABS; i++) {
  126.         tables [i] = 0;
  127.     }
  128.  
  129.     /* main loop */
  130.  
  131.     for(;;) {
  132.         printf("\nEnter table number or ");
  133.         printf("-1 to exit or ");
  134.         printf("-2 to dump tables.\n");
  135.  
  136.         _gets(inbuf);
  137.         number = atoi(inbuf);
  138.         if (number == -1) {
  139.             return;
  140.         }
  141.         if (number == -2) {
  142.             for (i = 0; i < NTABS; i++) {
  143.                 if (tables [i] != 0) {
  144.             printf("\nDump of table %d\n",i);
  145.                     dumptabl (tables [i]);
  146.                 }
  147.             }
  148.             continue;
  149.         }
  150.         if (number < 0 || number >= NTABS) {
  151.             printf("Bad table number\n");
  152.             continue;
  153.         }
  154.  
  155.         /* create table if needed */
  156.         if (tables [number] == 0) {
  157.             printf("Creating table %d\n",number);
  158.             tables [number] = mktabl(33);
  159.             printf("Table %d at %x\n",
  160.                 number, tables [number]);
  161.         }
  162.  
  163.         /* get name of symbol */
  164.         printf("Enter symbol name\n");
  165.         _gets(symbol);
  166.         if (symbol [0] == 0) {
  167.             continue;
  168.         }
  169.  
  170.         /* delete if info field is null */
  171.         printf("Enter info field or CR\n");
  172.         _gets(info);
  173.                 if (info [0] == 0) {
  174.             delete(symbol, tables [number]);
  175.         }
  176.         else {
  177.             enter(symbol, info, tables [number]);
  178.         }
  179.     }
  180. }
  181.  
  182. /*  delete - remove a symbol from the symbol table */
  183.  
  184. delete (symbol, table)
  185. char *symbol;
  186. struct symtab *table;
  187. {
  188.     int h;
  189.     struct node   *n, *n1;
  190.  
  191.     /* comment out -----
  192.     printf("In delete:  symbol = %s,  table = %x\n",
  193.         symbol, table);
  194.     ----- end comment out */
  195.  
  196.     /* point at list of buckets */
  197.     h = hashfunc(symbol, table -> htsize);
  198.     n = table -> hashtab [h];
  199.  
  200.     /* the first bucket is a special case so that the code
  201.      * is independent of the format of struct symtab.
  202.      */
  203.     if (n == 0) {
  204.         return;
  205.     }
  206.     if (equal(symbol, n -> data)) {
  207.         table -> hashtab [h] = n -> next;
  208.         dsfree(n);
  209.         return;
  210.     }
  211.  
  212.     /* general case:  search list of buckets */
  213.        
  214.     n1 = n;        /* n1 points at previous bucket */
  215.     n  = n -> next;    /* n  points at current bucket */
  216.  
  217.     while (n) {
  218.         if (equal(symbol, n -> data)) {
  219.             n1 -> next = n -> next;
  220.             dsfree(n);
  221.             return;
  222.         }
  223.         else {
  224.             n1 = n;
  225.             n  = n -> next;
  226.         }
  227.     }
  228. }
  229.  
  230. /* dumptabl -- dump all symbols of a symbol table */
  231.  
  232. dumptabl (table)
  233. struct symtab *table;
  234. {
  235.     int i, k, posn;
  236.     char *n, *symbol, *info;
  237.     int  *p;
  238.  
  239.     /* dump hash table */
  240.     printf("The hash table is:\n\n");
  241.     for (i = 0; i < table -> htsize; i++) {
  242.         if (k = table -> hashtab [i]) {
  243.             printf("hashtab [%3d] = %x\n",
  244.                 i, k);
  245.         }
  246.     }
  247.  
  248.     /* print all the nodes in the table */
  249.     posn = 0;
  250.     while (symbol = sctabl(table, &posn)) {
  251.         info = symbol;
  252.         while (*info++ != EOS) {
  253.             ;
  254.         }
  255.         p = symbol - 2;
  256.         printf("node = %x,  ", symbol);
  257.         printf("next = %x,  ", *p);
  258.         printf("symbol = %s,  ", symbol);
  259.         printf("info = %s\n", info);
  260.     }
  261. }
  262.         
  263.  
  264. /*  enter -- place a symbol in the symbol table
  265.  *           update entry if already present
  266.  */
  267.  
  268. enter (symbol, info, table)
  269. char *symbol, *info;
  270. struct symtab *table;
  271. {
  272.     struct node *n;
  273.     int  i, h, k;
  274.  
  275.     /* allocate another node */
  276.     k = (length(symbol) + 1) + (length(info) + 1) + NHEAD;
  277.  
  278.     /* use a cast for maximum portability:
  279.      *  n = (struct * node) dsget (k);
  280.      */
  281.     n = dsget (k);
  282.  
  283.     /* set header fields of node */
  284.     n -> nchk = NODE;
  285.  
  286.     /* copy symbol and info to data area */
  287.     i = 0;
  288.     stcopy (symbol, 0, n -> data, &i);
  289.     i++;
  290.     scopy (info, 0, n -> data, i);
  291.  
  292.     /* hang node from hash table */
  293.     h = hashfunc(symbol, table -> htsize);
  294.     n -> next = table -> hashtab [h];
  295.     table -> hashtab [h] = n;
  296. }
  297.  
  298. /* compute the hash function for symbol in a table with
  299.  * n entries.
  300.  */
  301.  
  302. hashfunc (symbol, n)
  303. char *symbol;
  304. int  n;
  305. {
  306.     int i, h;
  307.  
  308.     h = 0;
  309.     for (i = 0; symbol[i] != EOS; i++) {
  310.         h += symbol [i];
  311.     }
  312.     return (h%n);
  313. }
  314.  
  315. /*  lookup - return pointer to info for symbol in table.
  316.  *         -- return 0 if symbol not in table
  317.  */
  318.  
  319. char *lookup (symbol, table)
  320. char *symbol;
  321. struct symtab * table;
  322. {
  323.     int h;
  324.     struct node *n;
  325.     char *p;
  326.  
  327.     h = hashfunc(symbol, table -> htsize);
  328.     n = table -> hashtab [h];
  329.  
  330.     for ( ; n; n = n -> next) {
  331.         if (equal(symbol, n -> data)) {
  332.             /* point p at info field */
  333.             p = n -> data;
  334.             while (*p++ != EOS) {
  335.                 ;
  336.             }
  337.             return(p);
  338.         }
  339.     }
  340.     return (0);
  341. }
  342.  
  343. /*  mktabl - make a new (empty) symbol table */
  344.  
  345. char *mktabl (hashsize)
  346. int hashsize;
  347. {
  348.     char *dsget();
  349.     struct symtab *table;
  350.     int i;
  351.  
  352.     /* get storage for the table.
  353.      * use a cast for maximum portability:
  354.      * table = (symtab *) dsget (...);
  355.      */
  356.     table = dsget ((2 * hashsize) + STHEAD);
  357.  
  358.     /* fill in the debugging byte */
  359.     table -> stchk = TABCHK;
  360.  
  361.     /* fill in the size of the table */
  362.     table -> htsize = hashsize;
  363.  
  364.     /* zero out the hash table */
  365.     for (i = 0; i < hashsize; i++) {
  366.         table -> hashtab [i] = 0;
  367.     }
  368.     return(table);
  369. }
  370.         
  371. /*  rmtabl - remove a symbol table, deleting all entries */
  372.  
  373. rmtabl (table)
  374. struct symtab *table;
  375. {
  376.     struct node *n, *n1;
  377.     int  i;
  378.  
  379.     /* check debugging byte */
  380.     if (table -> stchk != TABCHK) {
  381.         syserr ("rmtabl:  bad check byte");
  382.     }
  383.  
  384.     /* free every entry in hash table */
  385.     for (i = 0; i < table -> htsize; i++) {
  386.         n = table -> hashtab [i];
  387.         while (n) {
  388.             n1 = n -> next;
  389.             dsfree(n);
  390.             n = n1;
  391.         }
  392.     }
  393.             
  394.     /* free the symbol table itself.
  395.      * a cast would be best:  dsfree( (char *) table);
  396.      */
  397.     dsfree(table);
  398.     printf("End of rmtabl\n");
  399. }
  400.  
  401. /*  sctabl -- scan symbol table.
  402.  *            update *posn.
  403.  *            return pointer to data field or 0.
  404.  */
  405.  
  406. char *sctabl (table, posn)
  407. struct symtab *table;
  408. int *posn;
  409. {
  410.     int i, count;
  411.     struct node *n;
  412.  
  413.     count = 0;
  414.     for (i = 0; i < table -> htsize; i++) {
  415.         n = table -> hashtab [i];
  416.         while (n) {
  417.             if (count == *posn) {
  418.                 (*posn)++;
  419.                 return (n -> data);
  420.             }
  421.             else {
  422.                 count++;
  423.                 n = n -> next;
  424.             }
  425.         }
  426.     }
  427.     (*posn)++;
  428.     return(0);
  429. }
  430.  
  431. 
  432. /*  sctabl -- scan symbol table.
  433.  *            update *posn.
  434.  *            return pointer to data field or 0.
  435.  */
  436.  
  437. char *sctabl (table, posn)
  438. struct symtab *table;
  439. int *posn;
  440. {
  441.     int i, count;
  442.     struct node *n;
  443.  
  444.     count = 0;
  445.     for (i = 0; i <